/*
 * 9.2
 * Write a method to sort an array of strings so that all the anagrams are next to each
 * other.
 */
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;

bool compare_pair(const pair<string, string> &p1, const pair<string, string> &p2)
{
    return p1.first < p2.first;
}

/* XXX: This is totally wrong, since std::map is single key. */
void anagram_sort_old(vector<string> &v)
{
    map<string, string> m; // XXX: the compare function should be passed here, and map is always sorted by _key_!!!
    for (vector<string>::const_iterator it = v.begin(); it != v.end(); ++it) {
        string s = *it;
        std::sort(s.begin(), s.end());
        m[s] = *it;
    }
    v.clear();
    for (map<string, string>::const_iterator it = m.begin(); it != m.end(); ++it) {
        v.push_back(it->first);
    }
}

void anagram_sort(vector<string> &v)
{
    vector<pair<string, string> > vp;
    for (vector<string>::const_iterator it = v.begin(); it != v.end(); ++it) {
        string s = *it;
        std::sort(s.begin(), s.end());
        vp.push_back(pair<string, string>(s, *it));
    }
    std::sort(vp.begin(), vp.end(), compare_pair);
    v.clear();
    for (vector<pair<string, string> >::const_iterator it = vp.begin(); it != vp.end(); ++it) {
        v.push_back(it->second);
    }
}

int main()
{
    const char *strs[] = { "213", "111", "121", "222", "112", "221", "312" };
    vector<string> v;
    for (int i = 0; i < sizeof(strs)/sizeof(strs[0]); i++) {
        v.push_back(strs[i]);
    }
    anagram_sort(v);
    for (vector<string>::const_iterator it = v.begin(); it != v.end(); ++it) {
        cout << *it << endl;
    }
    return 0;
}
